<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
        <html><head>
        <link rel="stylesheet" type="text/css" href="apidocs.css"/>
        <title>API docs for &ldquo;sympy.ntheory.factor_&rdquo;</title>
        </head>
        <body><h1 class="module">Module s.n.factor_</h1><span id="part">Part of <a href="sympy.ntheory.html">sympy.ntheory</a></span><div class="toplevel"><div><p>Integer factorization</p>
</div></div><table class="children"><tr class="function"><td>Function</td><td><a href="#sympy.ntheory.factor_.multiplicity">multiplicity</a></td><td><div><p>Return the multiplicity of the number p in n; that is, the greatest</p>
</div></td></tr><tr class="function"><td>Function</td><td><a href="#sympy.ntheory.factor_.pollard_rho">pollard_rho</a></td><td><div><p>Use Pollard's rho method to try to extract a factor of n. The</p>
</div></td></tr><tr class="function"><td>Function</td><td><a href="#sympy.ntheory.factor_.pollard_pm1">pollard_pm1</a></td><td><div><p>Use Pollard's p-1 method to try to extract a factor of n. The</p>
</div></td></tr><tr class="function"><td>Function</td><td><a href="#sympy.ntheory.factor_.trial">trial</a></td><td><div><p>Factor n as far as possible through trial division, taking</p>
</div></td></tr><tr class="function"><td>Function</td><td><a href="#sympy.ntheory.factor_.factorint">factorint</a></td><td><div><p>Given a positive integer n, factorint(n) returns a list</p>
</div></td></tr><tr class="function"><td>Function</td><td><a href="#sympy.ntheory.factor_.primefactors">primefactors</a></td><td><div><p>Return a list of n's prime factors, ignoring multiplicity.</p>
</div></td></tr><tr class="function"><td>Function</td><td><a href="#sympy.ntheory.factor_.divisors">divisors</a></td><td><div><p>Return a list of all positive integer divisors of n.</p>
</div></td></tr><tr class="function"><td>Function</td><td><a href="#sympy.ntheory.factor_.totient">totient</a></td><td><div><p>Calculate the Euler totient function phi(n)</p>
</div></td></tr></table>
            <div class="function">
            <div class="functionHeader">def <a name="sympy.ntheory.factor_.multiplicity">multiplicity(p, n):</a></div>
            <div class="functionBody"><div><p>Return the multiplicity of the number p in n; that is, the greatest 
number m such that p**m divides n.</p>
<h1 class="heading">Example usage</h1>
<pre class="py-doctest">
<span class="py-prompt">&gt;&gt;&gt; </span>multiplicity(5, 8)
<span class="py-output">0</span>
<span class="py-output"></span><span class="py-prompt">&gt;&gt;&gt; </span>multiplicity(5, 5)
<span class="py-output">1</span>
<span class="py-output"></span><span class="py-prompt">&gt;&gt;&gt; </span>multiplicity(5, 25)
<span class="py-output">2</span>
<span class="py-output"></span><span class="py-prompt">&gt;&gt;&gt; </span>multiplicity(5, 125)
<span class="py-output">3</span>
<span class="py-output"></span><span class="py-prompt">&gt;&gt;&gt; </span>multiplicity(5, 250)
<span class="py-output">3</span></pre>
</div></div>
            </div>
            <div class="function">
            <div class="functionHeader">def <a name="sympy.ntheory.factor_.pollard_rho">pollard_rho(n, max_iters=5, seed=1234):</a></div>
            <div class="functionBody"><div><p>Use Pollard's rho method to try to extract a factor of n. The returned 
factor may be a composite number. A maximum of max_iters iterations are 
performed; if no factor is found, None is returned.</p>
<p>The rho algorithm is a Monte Carlo method whose outcome can be affected 
by changing the random seed value.</p>
<h1 class="heading">References</h1>
  <p>Richard Crandall &amp; Carl Pomerance (2005), &quot;Prime Numbers: A 
  Computational Perspective&quot;, Springer, 2nd edition, 229-231</p>
</div></div>
            </div>
            <div class="function">
            <div class="functionHeader">def <a name="sympy.ntheory.factor_.pollard_pm1">pollard_pm1(n, B=10, seed=1234):</a></div>
            <div class="functionBody"><div><p>Use Pollard's p-1 method to try to extract a factor of n. The returned 
factor may be a composite number. The search is performed up to a 
smoothness bound B; if no factor is found, None is returned.</p>
<p>The p-1 algorithm is a Monte Carlo method whose outcome can be affected 
by changing the random seed value.</p>
<h1 class="heading">Example usage</h1>
  <p>With the default smoothness bound, this number can't be cracked:</p>
<pre class="py-doctest">
<span class="py-prompt">&gt;&gt;&gt; </span>pollard_pm1(21477639576571)</pre>
  <p>Increasing the smoothness bound helps:</p>
<pre class="py-doctest">
<span class="py-prompt">&gt;&gt;&gt; </span>pollard_pm1(21477639576571, 2000)
<span class="py-output">4410317L</span></pre>
<h1 class="heading">References</h1>
  <p>Richard Crandall &amp; Carl Pomerance (2005), &quot;Prime Numbers: A 
  Computational Perspective&quot;, Springer, 2nd edition, 236-238</p>
</div></div>
            </div>
            <div class="function">
            <div class="functionHeader">def <a name="sympy.ntheory.factor_.trial">trial(n, candidates=None):</a></div>
            <div class="functionBody"><div><p>Factor n as far as possible through trial division, taking candidate 
factors from the given list. If no list of candidate factors is given, the 
prime numbers in the interval [2, sqrt(n)] are used, which guarantees a 
complete factorization.</p>
<p>The returned value is a list [(p1, e1), ...] such that n = p1**e1 * 
p2**e2 * ... If n could not be completely factored using numbers in the 
given range, the last p might be composite.</p>
<h1 class="heading">Example usage</h1>
  <p>A complete factorization:</p>
<pre class="py-doctest">
<span class="py-prompt">&gt;&gt;&gt; </span>trial(36960)
<span class="py-output">[(2, 5), (3, 1), (5, 1), (7, 1), (11, 1)]</span></pre>
  <p>This won't find the factors 7 and 11:</p>
<pre class="py-doctest">
<span class="py-prompt">&gt;&gt;&gt; </span>trial(36960, [2, 3, 5])
<span class="py-output">[(2, 5), (3, 1), (5, 1), (77, 1)]</span></pre>
</div></div>
            </div>
            <div class="function">
            <div class="functionHeader">def <a name="sympy.ntheory.factor_.factorint">factorint(n, limit=None, verbose=False):</a></div>
            <div class="functionBody"><div><p>Given a positive integer n, factorint(n) returns a list [(p_1, m_1), 
(p_2, m_2), ...] with all p prime and n = p_1**m_1 * p_2**m_2 * ...</p>
<p>Special cases: 1 factors as [], 0 factors as [(0, 1)], and negative 
integers factor as [(-1, 1), ...].</p>
<p>The function uses a composite algorithm, switching between Pollard's p-1
method and looking for small factors through trial division.</p>
<p>It is sometimes useful to look only for small factors. If 'limit' is 
specified, factorint will only perform trial division with candidate 
factors up to this limit (and p-1 search up to the same smoothness bound). 
As a result, the last 'prime' in the returned list may be composite.</p>
<h1 class="heading">Example usage</h1>
  <p>Here are some simple factorizations (with at most six digits in the 
  second largest factor). They should all complete within a fraction of a 
  second:</p>
<pre class="py-doctest">
<span class="py-prompt">&gt;&gt;&gt; </span>factorint(1)
<span class="py-output">[]</span></pre>
<pre class="py-doctest">
<span class="py-prompt">&gt;&gt;&gt; </span>factorint(100)
<span class="py-output">[(2, 2), (5, 2)]</span></pre>
<pre class="py-doctest">
<span class="py-prompt">&gt;&gt;&gt; </span>factorint(17*19)
<span class="py-output">[(17, 1), (19, 1)]</span></pre>
<pre class="py-doctest">
<span class="py-prompt">&gt;&gt;&gt; </span>factorint(prime(100)*prime(1000)*prime(10000))
<span class="py-output">[(541, 1), (7919, 1), (104729, 1)]</span></pre>
<pre class="py-doctest">
<span class="py-prompt">&gt;&gt;&gt; </span>factors = factorint(2**(2**6) + 1)
<span class="py-prompt">&gt;&gt;&gt; </span><span class="py-keyword">for</span> base, exp <span class="py-keyword">in</span> factors: <span class="py-keyword">print</span> base, exp
<span class="py-more">...</span>
<span class="py-output">274177 1</span>
<span class="py-output">67280421310721 1</span></pre>
  <p>Factors on the order of 10 digits can generally be found quickly. The 
  following computations should complete within a few seconds:</p>
<pre class="py-doctest">
<span class="py-prompt">&gt;&gt;&gt; </span>factors = factorint(21477639576571)
<span class="py-prompt">&gt;&gt;&gt; </span><span class="py-keyword">for</span> base, exp <span class="py-keyword">in</span> factors: <span class="py-keyword">print</span> base, exp
<span class="py-more">...</span>
<span class="py-output">4410317 1</span>
<span class="py-output">4869863 1</span></pre>
<pre class="py-doctest">
<span class="py-prompt">&gt;&gt;&gt; </span>factors = factorint(12345678910111213141516)
<span class="py-prompt">&gt;&gt;&gt; </span><span class="py-keyword">for</span> base, exp <span class="py-keyword">in</span> factors: <span class="py-keyword">print</span> base, exp
<span class="py-more">...</span>
<span class="py-output">2 2</span>
<span class="py-output">2507191691 1</span>
<span class="py-output">1231026625769 1</span></pre>
<pre class="py-doctest">
<span class="py-prompt">&gt;&gt;&gt; </span>factors = factorint(5715365922033905625269)
<span class="py-prompt">&gt;&gt;&gt; </span><span class="py-keyword">for</span> base, exp <span class="py-keyword">in</span> factors: <span class="py-keyword">print</span> base, exp
<span class="py-more">...</span>
<span class="py-output">74358036521 1</span>
<span class="py-output">76862786989 1</span></pre>
  <p>This number has an enormous semiprime factor that is better 
  ignored:</p>
<pre class="py-doctest">
<span class="py-prompt">&gt;&gt;&gt; </span>a = 1407633717262338957430697921446883
<span class="py-prompt">&gt;&gt;&gt; </span>factorint(a, limit=10000)
<span class="py-output">[(7, 1), (991, 1), (202916782076162456022877024859L, 1)]</span>
<span class="py-output"></span><span class="py-prompt">&gt;&gt;&gt; </span>isprime(_[-1][0])
<span class="py-output">False</span></pre>
</div></div>
            </div>
            <div class="function">
            <div class="functionHeader">def <a name="sympy.ntheory.factor_.primefactors">primefactors(n, limit=None, verbose=False):</a></div>
            <div class="functionBody"><div><p>Return a list of n's prime factors, ignoring multiplicity. Unlike 
factorint(), primefactors() only returns prime numbers; i.e., it does not 
return -1 or 0, and if 'limit' is set too low for all factors to be found, 
composite factors are ignored.</p>
<h1 class="heading">Example usage</h1>
<pre class="py-doctest">
<span class="py-prompt">&gt;&gt;&gt; </span>primefactors(6)
<span class="py-output">[2, 3]</span>
<span class="py-output"></span><span class="py-prompt">&gt;&gt;&gt; </span>primefactors(-5)
<span class="py-output">[5]</span></pre>
<pre class="py-doctest">
<span class="py-prompt">&gt;&gt;&gt; </span>factorint(123456)
<span class="py-output">[(2, 6), (3, 1), (643, 1)]</span>
<span class="py-output"></span><span class="py-prompt">&gt;&gt;&gt; </span>primefactors(123456)
<span class="py-output">[2, 3, 643]</span></pre>
<pre class="py-doctest">
<span class="py-prompt">&gt;&gt;&gt; </span>factorint(10000000001, limit=1000)
<span class="py-output">[(101, 1), (99009901, 1)]</span>
<span class="py-output"></span><span class="py-prompt">&gt;&gt;&gt; </span>isprime(99009901)
<span class="py-output">False</span>
<span class="py-output"></span><span class="py-prompt">&gt;&gt;&gt; </span>primefactors(10000000001, limit=1000)
<span class="py-output">[101]</span></pre>
</div></div>
            </div>
            <div class="function">
            <div class="functionHeader">def <a name="sympy.ntheory.factor_.divisors">divisors(n):</a></div>
            <div class="functionBody"><div><p>Return a list of all positive integer divisors of n.</p>
<pre class="py-doctest">
<span class="py-prompt">&gt;&gt;&gt; </span>divisors(24)
<span class="py-output">[1, 2, 3, 4, 6, 8, 12, 24]</span></pre>
</div></div>
            </div>
            <div class="function">
            <div class="functionHeader">def <a name="sympy.ntheory.factor_.totient">totient(n):</a></div>
            <div class="functionBody"><div><p>Calculate the Euler totient function phi(n)</p>
<pre class="py-doctest">
<span class="py-prompt">&gt;&gt;&gt; </span>totient(1)
<span class="py-output">1</span>
<span class="py-output"></span><span class="py-prompt">&gt;&gt;&gt; </span>totient(25)
<span class="py-output">20</span></pre>
</div></div>
            </div></body>
        